Field of the Invention
Embodiments of the present invention relate generally to content delivery and distribution and, more specifically, to Gaussian ranking using matrix factorization.
Description of the Related Art
Many applications attempt to organize and/or convey items in a meaningful manner to users by implementing a ranking engine that attempts to rank items according to one or more metrics for a given user in real-time. For example, a video distribution application may execute a ranking engine that ranks videos based on the viewing history of a user. In conjunction with the ranking, the video distribution system also may display information related to the highest ranked videos in an attempt to convince the user that he or she would enjoy those videos and entice the user to select one or more of the videos to view.
To compute rankings for a given user, a typical ranking engine includes a trained ranking model that estimates a continuous-value score for each item in a list based on one or more factors and then ranks the items based on the scores. Accordingly, the quality of the rankings and the time required to perform ranking operations are dependent on the trained ranking model. Oftentimes, machine learning techniques are used to train the ranking model by minimizing a “rank loss” function that measures a deviation of the predicted ranks computed via the ranking model from the “true” ranks based on training data. Prior to training a ranking model, a particular rank loss function is chosen. For example, minimizing a particular rank loss function could maximize a normalized Discounted Cumulative Gain (nDGC) metric that emphasizes the ranking quality of the items at the head of a ranked list of items. For each user, a ranking model that is trained based on such a “nDGC” rank loss function produces more accurate rankings for items at the head of a ranked list and less accurate rankings for items at the tail of the ranked list.
Conventional optimization techniques that are considered to be computationally efficient, such as stochastic gradient descent, typically rely on the specific properties of the metrics that the training algorithm is designed to optimize in achieving computational efficiencies. In particular, when minimizing a rank loss function to optimize a ranking metric, conventional optimization techniques require a smooth mapping between scores and ranks. However, the actual mapping from scores to ranks is usually not smooth, meaning that, for example small changes in scores can result in disproportionately large changes in ranks. Therefore, ranking engines typically cannot implement these types of computationally efficient optimization techniques to directly optimize rank loss functions.
In view of the foregoing, some ranking engines directly optimize the rank loss function via less efficient conventional optimization techniques. However, the inherent inefficiencies associated with those techniques can cause the time required to directly optimize the ranking model to be unacceptably long. Other ranking engines attempt to use smooth approximations to rank loss functions that optimize approximate ranking metrics, where the approximate ranking metrics are associated with smooth mappings between scores and ranks. Subsequently, such ranking engines optimize the smooth approximations via computationally efficient optimization techniques. However, developing smooth approximations is typically a time consuming, manually-based process. Further, smooth approximations decrease the accuracy of the rankings produced when the trained ranking model is implemented.
As the foregoing illustrates, what is needed in the art are more effective techniques for training ranking models via rank loss functions.